package Maze

import (
	"fmt"
)

var maze [] [] int = [][]int{}

func init() {
	fmt.Println("init maze ....")

	maze = [][]int{
		{0, 1, 1, 1, 1, 1, 1, 1, 1, 1}, //0
		{0, 0, 0, 1, 1, 1, 1, 1, 1, 1}, //1
		{1, 0, 0, 1, 1, 1, 1, 1, 1, 1}, //2
		{1, 0, 0, 0, 1, 1, 1, 0, 1, 1}, //3
		{1, 0, 1, 1, 1, 1, 1, 1, 1, 1}, //4
		{1, 0, 0, 0, 1, 0, 0, 0, 0, 1}, //5
		{1, 0, 1, 0, 0, 0, 1, 0, 0, 1}, //6
		{1, 0, 1, 1, 1, 0, 1, 1, 0, 1}, //7
		{1, 0, 1, 1, 1, 0, 1, 0, 0, 1}, //8
		{1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, //9
	} // 0  1  2  3  4  5  6  7  8  9
}

type point struct {
	x int //行
	y int // 列
}

func (p point) add(r point) (point) {

	return point{p.x + r.x, p.y + r.y}
}

func (p point) check(grid [][]int) (int, bool) {

	if p.x < 0 || p.x > len(grid)-1 {

		return 0, false
	}

	if p.y < 0 || p.y > len(grid[p.x])-1 {
		return 0, false
	}

	return grid[p.x][p.y], true
}

var dirs [] point = [] point{{-1, 0}, {1, -1}, {1, 0}, {0, 1}}

func main() {

	steps := walk(point{0, 0}, point{9, 9})

	for _, row := range steps {
		for _, val := range row {
			/*			if val == 0  {
							fmt.Printf("%3d", 1)
							continue
						}*/

			fmt.Printf("%3d", val)
		}
		fmt.Println()
	}
}

func walk(start, end point) (steps [][]int) {

	steps = make([][]int, len(maze))

	for i := range steps {
		steps[i] = make([]int, len(maze[i]))

	}

	q := [] point{start}

	for len(q) > 0 {

		current := q[0]

		q = q[1:]

		if end == current {
			break
		}

		for _, dir := range dirs {

			next := current.add(dir)

			if next == start {
				continue
			}

			if position, isPass := next.check(maze); !isPass || position == 1 {

				continue
			}
			if position, isPass := next.check(steps); !isPass || position != 0 {

				continue
			}

			curSteps, _ := current.check(steps)

			steps[next.x][next.y] = curSteps + 1

			q = append(q, next)

		}
	}


	return steps
}
